Nakamoto consensus
Longest-chain fork-choice rule & proof-of-work
Security properties
Juan A. Garay, Aggelos Kiayias, Nikos Leonardos
Eurocrypt'15, Related Slide by Kiayias Originally in the lock-step model, updated for non-lock-step
Rafael Pass (Cornell Tech), Lior Seeman (Harvard University), abhi shelat (U of Virginia)
Hybrid Freezing Model for simplicity and prove that it's OK
Towards better bounds
Lucianna Kiffer, Rajmohan Rajaraman and abhi shelat (Northeastern University)
Prove the consistency (Definition 2.1) of Longest-chain, GHOST, CliqueChain (a variation of the Chainweb) with Markov-chain-based framework
Ling Ren (UIUC)
Continuous time (no "round"), ideal lottery instead of random oracle model
Peter Gaˇzi, Aggelos Kiayias, and Alexander Russell (IOHK)
CCS'20
Proofs in different approches/models
Christian Badertscher (ETH), Ueli Maurer (ETH), Daniel Tschudi (Aarhus), and Vassilis Zikas (Edinburgh)
UC model of the Bitcoin blockchain and of general permissionless blockchains
Alexandru Cojocaru, Juan Garay, Aggelos Kiayias, Fang Song, Petros Wallden
Juan Garay and Yu Shen
Suryanarayana Sankagiri (UIUC), Shreyas Gandlur, Bruce Hajek
Weakening the assumptions
Puwen Wei Quan Yuan (Shandong University), and Yuliang Zheng (University of Alaba)
AsiaCrypto'18
Improve to tolerate Long delay attack (network delay larger than the mining rate)
Redefine the properties of chain growth rate and common prefix
Georgia Avarikioti, Lukas K ̈appeli, Yuyi Wang, and Roger Wattenhofer (ETH Zurich)
Extension to Garay et al.
(Abstract) We prove Bitcoin is secure under temporary dishonest majority. We assume the adversary can corrupt a specific fraction of parties and also introduce crash failures, i.e., some honest participants are offline during the execution of the protocol. We demand a majority of honest on-line participants on expectation. We explore three different models and present the requirements for proving Bitcoin’s security in all of them. We first examine a synchronous model, then extend to a bounded delay model and last we consider a synchronous model that allows message losses.
FC'19
Juan A. Garay, Aggelos Kiayias, Nikos Leonardos, Giorgos Panagiotakos
IACR PKC '18
Bootstrap the genesis block
Juan Garay, Aggelos Kiayias, and Nikos Leonardos
Prove that Nakamoto’s protocol achieves, under suitable conditions, consistency and liveness in bounded-delay networks with adaptive (as opposed to predetermined) dynamic participation assuming, as in previous works, that the majority of the computational power favors the honest parties.
Difficulty adjustment
Juan A. Garay, Aggelos Kiayias, Nikos Leonardos
Dmitry Meshko (IOHK) et al.
Shunya Noda, Kyohei Okumura, Yoshinori Hashimoto
Others
Improvements
George Bissias Brian N. Levine (UMass Amherst)
Origin of PoW
Cynthia Dwork (IBM), Moni Naor
Markus Jakobsson
Survey
Nicholas Stifter∗†, Aljosha Judmayer∗, Philipp Schindler∗, Alexei Zamyatin‡∗, Edgar Weippl∗†
∗SBA Research, ‡Imperial College London, †Christian Doppler Laboratory for Security and Quality Improvement in the Production System Lifecycle (CDL-SQI), TU Wien